use crate::stools::random_array;
use std::{cmp::PartialOrd, collections::VecDeque};

fn get_bottom<T>(v: &mut Vec<T>) -> T {
    if v.len() == 1 {
        return v.pop().unwrap();
    }

    let a = v.pop().unwrap();
    let bottom = get_bottom(v);
    v.push(a);

    bottom
}

fn rev_stack<T>(v: &mut Vec<T>) {
    if v.is_empty() {
        return;
    }

    let bottom = get_bottom(v);
    rev_stack(v);
    v.push(bottom);
}

/// 用一个栈实现另一个栈的排序
/// 一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一
/// 个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序?
fn sort_stack<T: PartialOrd>(stack: &mut Vec<T>) {
    if stack.is_empty() {
        return;
    }
    let mut help: Vec<T> = vec![stack.pop().unwrap()];

    while let Some(cur) = stack.pop() {
        while !help.is_empty() && cur > help[help.len() - 1] {
            stack.push(help.pop().unwrap());
        }
        help.push(cur);
    }

    while let Some(cur) = help.pop() {
        stack.push(cur);
    }
}

/// 猫狗队列
/// 实现一种狗猫队列的结构，要求如下:
///  用户可以调用add方法将cat类或dog类的实例放入队列中;
///  用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出;
///  用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出;
///  用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出;
///  用户可以调用isEmpty方法，检查队列中是否还有dog或cat的实例;
///  用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例;
///  用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。
trait PetAction {
    fn add(&mut self, pet: Pet);
    fn pop_all(&mut self) -> Option<Pet>;
    fn pop_dog(&mut self) -> Option<Pet>;
    fn pop_cat(&mut self) -> Option<Pet>;
    fn is_empty(self) -> bool;
    fn is_dog_empty(self) -> bool;
    fn is_cat_empty(self) -> bool;
}

#[derive(Debug)]
enum Pet {
    Dog(Dog),
    Cat(Cat),
}
impl ReadInfo for Pet {
    fn get_type(&self) -> &str {
        match self {
            Pet::Dog(pet) => pet.get_type(),
            Pet::Cat(pet) => pet.get_type(),
        }
    }
    fn get_num(&self) -> usize {
        match self {
            Pet::Dog(dog) => dog.get_num(),
            Pet::Cat(cat) => cat.get_num(),
        }
    }
}

trait ReadInfo {
    fn get_type(&self) -> &str;
    fn get_num(&self) -> usize;
}
#[derive(Debug)]
struct Dog {
    name: &'static str,
    num: usize,
}
impl Dog {
    fn new(num: usize) -> Self {
        Self { name: "dog", num }
    }
}
impl ReadInfo for Dog {
    fn get_type(&self) -> &str {
        self.name
    }
    fn get_num(&self) -> usize {
        self.num
    }
}

#[derive(Debug)]
struct Cat {
    name: &'static str,
    num: usize,
}
impl Cat {
    fn new(num: usize) -> Self {
        Self { name: "cat", num }
    }
}
impl ReadInfo for Cat {
    fn get_type(&self) -> &str {
        self.name
    }
    fn get_num(&self) -> usize {
        self.num
    }
}
struct DogCatQueue {
    dog: VecDeque<Pet>,
    cat: VecDeque<Pet>,
    count: usize,
}
impl DogCatQueue {
    fn new() -> Self {
        Self {
            dog: VecDeque::new(),
            cat: VecDeque::new(),
            count: 0,
        }
    }
}
impl PetAction for DogCatQueue {
    fn add(&mut self, pet: Pet) {
        self.count += 1;
        match pet.get_type() {
            "dog" => self.dog.push_front(Pet::Dog(Dog::new(self.count))),
            "cat" => self.cat.push_front(Pet::Cat(Cat::new(self.count))),
            _ => panic!("undefined pet type"),
        }
    }

    fn is_dog_empty(self) -> bool {
        self.dog.is_empty()
    }

    fn is_cat_empty(self) -> bool {
        self.cat.is_empty()
    }

    fn pop_all(&mut self) -> Option<Pet> {
        if !self.dog.is_empty() && !self.cat.is_empty() {
            if self.dog.back().unwrap().get_num() > self.cat.back().unwrap().get_num() {
                self.cat.pop_back()
            } else {
                self.dog.pop_back()
            }
        } else if self.dog.is_empty() {
            self.cat.pop_back()
        } else {
            self.dog.pop_back()
        }
    }

    fn pop_cat(&mut self) -> Option<Pet> {
        self.cat.pop_back()
    }
    fn pop_dog(&mut self) -> Option<Pet> {
        self.dog.pop_back()
    }

    fn is_empty(self) -> bool {
        self.dog.is_empty() && self.cat.is_empty()
    }
}

pub fn leetcode_main() {
    let mut v = random_array(10, 0..100);
    println!("v: {:?}", v);
    rev_stack(&mut v);
    println!("rev(v): {:?}", v);
    sort_stack(&mut v);
    println!("sort(v): {:?}", v);

    let mut dog_cat_queue = DogCatQueue::new();
    dog_cat_queue.add(Pet::Dog(Dog::new(0)));
    dog_cat_queue.add(Pet::Dog(Dog::new(0)));
    dog_cat_queue.add(Pet::Cat(Cat::new(0)));
    dog_cat_queue.add(Pet::Dog(Dog::new(0)));
    dog_cat_queue.add(Pet::Cat(Cat::new(0)));
    dog_cat_queue.add(Pet::Dog(Dog::new(0)));
    while let Some(pet) = dog_cat_queue.pop_all() {
        println!("pet: {:?}", pet);
    }
}
